#pragma once
#include<vector>
using namespace std;
template<class T>
class Greater
{
public:
	bool operator()(const T& x,const T& y)
	{
		return x > y;
	}
};
template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};
template<class T, class container = vector<T>,class compare = Less<T>>
class priority_queue
{
public:
	void adjust_up(size_t child)
	{
		compare com;
		size_t parent = (child - 1) / 2;
		while (child > 0)
		{
			if (com(_con[child] , _con[parent]))
			{
				swap(_con[child], _con[parent]);
				child = parent;
				parent = (parent - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}
	void push(const T& val)
	{
		_con.push_back(val);
		adjust_up(_con.size() - 1);
	}
	void adjust_down(size_t parent)
	{
		compare com;
		size_t child = parent * 2 + 1;
		while (child < _con.size())
		{
			if (child + 1 < _con.size() && com(_con[child + 1] , _con[child]))
			{
				++child;
			}
			if (com(_con[child] , _con[parent]))
			{
				swap(_con[child], _con[parent]);
				parent = child;
				child = child * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}
	void pop()
	{
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		adjust_down(0);
	}
	bool empty()
	{
		return _con.empty();
	}
	T& top()
	{
		return _con.front();
	}
	size_t size()
	{
		return _con.size();
	}
private:
	container _con;

};
void test1()
{
	priority_queue<int> pq;
	pq.push(1);
	pq.push(2);
	pq.push(3);
	pq.push(4);
	pq.push(5);
	pq.push(6);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}

}